package leetcode.top100;

import utils.TreeNode;

import java.util.Stack;

/**
 * 给定一个二叉树，原地将它展开为链表。
 *
 * 例如，给定二叉树
 *
 *     1
 *    / \
 *   2   5
 *  / \   \
 * 3   4   6
 * 将其展开为：
 *
 * 1
 *  \
 *   2
 *    \
 *     3
 *      \
 *       4
 *        \
 *         5
 *          \
 *           6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020/4/8 22:10
 */
public class Code114_ConvertBTtoList {
    //先序遍历展开
    public void flatten(TreeNode root) {
        if(root == null) return;
        process(root);
    }

    /**
     * 先序遍历，如果使用递归，当前节点的右孩子会丢失。
     * 所以使用循环，stack可以保存右孩子，不会丢失
     */
    private void process(TreeNode root) {
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode pre = null;
        while (!stack.isEmpty()){
            root = stack.pop();
            if(pre != null){
                pre.right = root;
                pre.left = null;
            }
            if(root.right != null) stack.push(root.right);
            if(root.left != null) stack.push(root.left);
            pre = root;
        }
    }
}
